--[[
map's v={
k={k1=v1,...}: key for complete match
p={v1,v2,v3,...}: patten for function _match, from 1 to #p
nosub=true|false: not sub dpl handle

}
--]]
module(..., package.seeall)

require'zdc.node'
require'zdc.typeex'
require'zdc.dpl'
require'zdc.idutil'

Tree = {}
local Tree_mt = {__metatable={}, __index=Tree}

function new()
	local obj = setmetatable({tr={}}, Tree_mt)
	return obj
end

function Tree:_clear_all()
	self.tr={}
end

function Tree:_query(id)
	local lastv
	local tr=self.tr
	for s in string.gmatch(id,'[^/]+') do
		if tr.v and not tr.nosub then lastv=tr end
		local k=tr.k
		local c=k and k[s]
		if not c then
			local p=tr.p
			if p then
				for i=1,#p do
					local t=p[i]
					if t._match(s) then
						c=t
						break
					end
				end
			end
		end
		if c==nil then
			return lastv
		end
		tr=c
	end
	if tr.v then return tr end
	return lastv
end
local function fetch_tree(tr,subs)
	local t=tr.v
	if t then table.insert(subs,t) end
	t=tr.k
	if t then
		for k,v in pairs(t) do
			if v.v then table.insert(subs,v) end
			fetch_all(v,subs)
		end
	end
	t=tr.p
	if t then
		for _,v in ipairs(t) do
			if v.v then table.insert(subs,v) end
			fetch_all(v,subs)
		end
	end
	return subs
end
function Tree:_do_every(fun)
	return self:__do_every__(self.tr,fun)
end

function Tree:__do_every__(tr,fun)
	local t=tr.v
	if t then
		local r1,r2,r3=fun(tr)
		if r1 then return r1,r2,r3 end
	end
	t=tr.k
	if t then
		for k,v in pairs(t) do
			local r1,r2,r3=self:__do_every__(v,fun)
			if r1 then return r1,r2,r3 end
		end
	end
	t=tr.p
	if t then
		for _,v in ipairs(t) do
			local r1,r2,r3=self:__do_every__(v,fun)
			if r1 then return r1,r2,r3 end
		end
	end
	return 
end

function Tree:_query_subs(id)
	local lastv
	local tr=self.tr
	for s in string.gmatch(id,'[^/]+') do
		if tr.v and not tr.nosub then lastv=tr end
		local k=tr.k
		local c=k and k[s]
		if not c then
			local p=tr.p
			if p then
				for i=1,#p do
					local t=p[i]
					if t._match(s) then
						c=t
						break
					end
				end
			end
		end
		if c==nil then
			tr=nil
			break
		end
		tr=c
	end
	local subs={}
	if not tr or not tr.v or tr.nosub then
		if lastv then
			table.insert(subs,lastv)
		end
	end
	if tr then
		fetch_tree(tr,subs)
	end
	return subs
end

function Tree:__build_path(tr,id)
	for s in string.gmatch(id,'[^/]+') do
		local k=tr.k
		local c=k and k[s]
		if not c then
			local p=tr.p
			if p then
				for i=1,#p do
					local t=p[i]
					if t._match(s) then
						c=t
						break
					end
				end
			end
		end
		if not c then
			if not k then
				k={}
				tr.k=k
			end
			c={}
			k[s]=c
		end
		tr=c
	end
	return tr
end

function Tree:_add_pattern(idlist,v,opt)
	if type(idlist)=='string' then
		idlist=zdc.idutil.GetSegment(idlist)
	end
	local poslst={}
	local tr=self.tr
	for i=1,#idlist do
		local seg=idlist[i]
		if type(seg)=='string' then
			tr=self:__build_path(tr,seg)
			poslst[#poslst+1]=seg
		else
			local p=tr.p
			if not p then
				p={}
				tr.p=p
			end
			--[[merge all key pattern
			if tr.k then
				for k,v in pairs(tr.k) do
					if seg._match(k) then
						
					end
				end
			end
			--]]
			local find
			for i=1,#p do
				if p[i]==seg.key then
					find=p[i]
					break
				end
			end
			if not find then
				find={key=seg.key;_match=seg._match}
				table.insert(p,find)
			end
			
			tr=find
			poslst[#poslst+1]=find.key or '__'
		end
	end
	if tr.v then error'dup id pattern' end
	tr.v=v
	if opt then
		for k,v in pairs(opt) do
			tr[k]=v
		end
	end
	tr.pos=table.concat(poslst,'/')
	return tr
end
